from typing import List

from sortedcontainers import SortedList


class Solution:
    def kEmptySlots(self, bulbs: List[int], k: int) -> int:
        # 定义当前灯泡打开状态
        now = SortedList()

        for time, bulb in enumerate(bulbs):
            left = now.bisect_left(bulb) - 1
            right = now.bisect_right(bulb)

            if left != -1 and bulb - now[left] == k + 1:
                return time + 1
            if right != len(now) and now[right] - bulb == k + 1:
                return time + 1

            now.add(bulb)

        return -1


if __name__ == "__main__":
    print(Solution().kEmptySlots([1, 3, 2], 1))  # 2
    print(Solution().kEmptySlots([1, 2, 3], 1))  # -1

    # 测试用例21/61
    print(Solution().kEmptySlots([6, 5, 8, 9, 7, 1, 10, 2, 3, 4], 2))  # 8
